package com.origin.niuke.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * NC124 字典树的实现
 * 算法：字典树
 *
 * @author yezh
 * @version 1.0
 * @date 2022/10/26 21:46
 */
public class NC124 {

    public String[] trieU (String[][] operators) {
        List<String> ans = new ArrayList<>();
        Trie trie = new Trie();
        for (String[] op : operators) {
            if ("1".equals(op[0])) trie.insert(op[1]);
            else if ("2".equals(op[0])) trie.delete(op[1]);
            else if ("3".equals(op[0])) ans.add(trie.search(op[1]) ? "YES" : "NO");
            else if ("4".equals(op[0])) ans.add(trie.prefixNumber(op[1]) + "");
        }
        return ans.toArray(new String[0]);
    }

    static class Trie {
        static class TrieNode {
            char c;
            TrieNode[] child;
            int num;
            boolean end;

            TrieNode(char c) {
                this.c = c;
                child = new TrieNode[26];
            }
        }

        TrieNode head;

        Trie() {
            head = new TrieNode(' ');
        }

        void insert(String word) {
            TrieNode cur = head;
            for (char c : word.toCharArray()) {
                if (cur.child[c - 'a'] == null) cur.child[c - 'a'] = new TrieNode(c);
                cur = cur.child[c - 'a'];
                ++cur.num;
            }
            cur.end = true;
        }

        void delete(String word) {
            TrieNode cur = head;
            for (char c : word.toCharArray()) {
                cur = cur.child[c - 'a'];
                --cur.num;
            }
            cur.end = false;
        }

        boolean search(String word) {
            TrieNode cur = head;
            for (char c : word.toCharArray()) {
                cur = cur.child[c - 'a'];
                if (cur == null || cur.num == 0) return false;
            }
            return true;
        }

        int prefixNumber(String pre) {
            TrieNode cur = head;
            for (char c : pre.toCharArray()) {
                cur = cur.child[c - 'a'];
                if (cur == null || cur.num == 0) return 0;
            }
            return cur.num;
        }

    }

}
